package com.example.demo.leetcode.classics150;

import java.util.ArrayList;
import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _105N皇后II
 * @description
 * @date 2023/08/11 23:25
 * <p>
 * ******************************************************
 */
public class _105N皇后II {

    int res = 0;

    public int totalNQueens(int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append('.');
            }
            board.add(sb.toString());
        }
        backtrack(board, 0);
        return res;
    }

    private void backtrack(List<String> board, int start) {
        if (board.size() == start) {
            res++;
            return;
        }

        for (int j = 0; j < board.size(); j++) {
            if (!checkValid(board, start, j)) {
                continue;
            }
            StringBuilder sb = new StringBuilder(board.get(start));
            sb.setCharAt(j, 'Q');
            board.set(start, sb.toString());
            backtrack(board, start + 1);
            sb.setCharAt(j, '.');
            board.set(start, sb.toString());
        }

    }

    private boolean checkValid(List<String> board, int row, int col) {

        for (int k = 0; k < board.size(); k++) {
            if (board.get(k).charAt(col) == 'Q') {
                return false;
            }
        }

        /* 检查右上方是否有皇后互相冲突 */
        for (int i = row - 1, j = col + 1;
             i >= 0 && j < board.size(); i--, j++) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        /* 检查左上方是否有皇后互相冲突 */
        for (int i = row - 1, j = col - 1;
             i >= 0 && j >= 0; i--, j--) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        _105N皇后II s = new _105N皇后II();
        System.out.println(s.totalNQueens(4));
    }
}
